{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Maximum Number of Removable Characters"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #array #string #binary-search"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数组 #字符串 #二分查找"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: maximumRemovals"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #可移除字符的最大数目"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你两个字符串 <code>s</code> 和 <code>p</code> ，其中 <code>p</code> 是 <code>s</code> 的一个 <strong>子序列</strong> 。同时，给你一个元素 <strong>互不相同</strong> 且下标 <strong>从 0 开始</strong> 计数的整数数组 <code>removable</code> ，该数组是 <code>s</code> 中下标的一个子集（<code>s</code> 的下标也 <strong>从 0 开始</strong> 计数）。</p>\n",
    "\n",
    "<p>请你找出一个整数 <code>k</code>（<code>0 <= k <= removable.length</code>），选出 <code>removable</code> 中的 <strong>前</strong> <code>k</code> 个下标，然后从 <code>s</code> 中移除这些下标对应的 <code>k</code> 个字符。整数 <code>k</code> 需满足：在执行完上述步骤后， <code>p</code> 仍然是 <code>s</code> 的一个 <strong>子序列</strong> 。更正式的解释是，对于每个 <code>0 <= i < k</code> ，先标记出位于 <code>s[removable[i]]</code> 的字符，接着移除所有标记过的字符，然后检查 <code>p</code> 是否仍然是 <code>s</code> 的一个子序列。</p>\n",
    "\n",
    "<p>返回你可以找出的 <strong>最大</strong><em> </em><code>k</code><em> </em>，满足在移除字符后<em> </em><code>p</code><em> </em>仍然是 <code>s</code> 的一个子序列。</p>\n",
    "\n",
    "<p>字符串的一个 <strong>子序列</strong> 是一个由原字符串生成的新字符串，生成过程中可能会移除原字符串中的一些字符（也可能不移除）但不改变剩余字符之间的相对顺序。</p>\n",
    "\n",
    "<p> </p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>s = \"abcacb\", p = \"ab\", removable = [3,1,0]\n",
    "<strong>输出：</strong>2\n",
    "<strong>解释：</strong>在移除下标 3 和 1 对应的字符后，\"a<strong>b</strong>c<strong>a</strong>cb\" 变成 \"accb\" 。\n",
    "\"ab\" 是 \"<strong>a</strong>cc<strong>b</strong>\" 的一个子序列。\n",
    "如果移除下标 3、1 和 0 对应的字符后，\"<strong>ab</strong>c<strong>a</strong>cb\" 变成 \"ccb\" ，那么 \"ab\" 就不再是 s 的一个子序列。\n",
    "因此，最大的 k 是 2 。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>s = \"abcbddddd\", p = \"abcd\", removable = [3,2,1,4,5,6]\n",
    "<strong>输出：</strong>1\n",
    "<strong>解释：</strong>在移除下标 3 对应的字符后，\"abc<strong>b</strong>ddddd\" 变成 \"abcddddd\" 。\n",
    "\"abcd\" 是 \"<strong>abcd</strong>dddd\" 的一个子序列。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>s = \"abcab\", p = \"abc\", removable = [0,1,2,3,4]\n",
    "<strong>输出：</strong>0\n",
    "<strong>解释：</strong>如果移除数组 removable 的第一个下标，\"abc\" 就不再是 s 的一个子序列。\n",
    "</pre>\n",
    "\n",
    "<p> </p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 <= p.length <= s.length <= 10<sup>5</sup></code></li>\n",
    "\t<li><code>0 <= removable.length < s.length</code></li>\n",
    "\t<li><code>0 <= removable[i] < s.length</code></li>\n",
    "\t<li><code>p</code> 是 <code>s</code> 的一个 <strong>子字符串</strong></li>\n",
    "\t<li><code>s</code> 和 <code>p</code> 都由小写英文字母组成</li>\n",
    "\t<li><code>removable</code> 中的元素 <strong>互不相同</strong></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [maximum-number-of-removable-characters](https://leetcode.cn/problems/maximum-number-of-removable-characters/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [maximum-number-of-removable-characters](https://leetcode.cn/problems/maximum-number-of-removable-characters/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['\"abcacb\"\\n\"ab\"\\n[3,1,0]', '\"abcbddddd\"\\n\"abcd\"\\n[3,2,1,4,5,6]', '\"abcab\"\\n\"abc\"\\n[0,1,2,3,4]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumRemovals(self, s: str, p: str, removable: List[int]) -> int:\n",
    "\n",
    "        ns, np = len(s), len(p)\n",
    "        n = len(removable)\n",
    "\n",
    "        def check(k):\n",
    "            state = [True] * ns\n",
    "            for i in range(k+1):\n",
    "                state[removable[i]] = False\n",
    "\n",
    "            j = 0\n",
    "            for i in range(ns):\n",
    "                if state[i] and s[i] == p[j]:\n",
    "                    j += 1\n",
    "                    if j == np:\n",
    "                        return True\n",
    "            return False\n",
    "        \n",
    "        l, r = 0, n - 1\n",
    "        if not check(0):\n",
    "            return 0\n",
    "        \n",
    "        while l < r:\n",
    "            mid = l + r + 1 >> 1\n",
    "            if check(mid):\n",
    "                l = mid\n",
    "            else:\n",
    "                r = mid - 1\n",
    "\n",
    "        return l + 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumRemovals(self, s: str, p: str, removable: List[int]) -> int:\n",
    "        slen, plen = len(s),len(p)\n",
    "        r_len = len(removable)\n",
    "\n",
    "        def check(k):\n",
    "            r = removable[:k]\n",
    "            r.sort()\n",
    "            rpos = 0\n",
    "            ppos = 0\n",
    "            for i in range(slen):\n",
    "                if rpos<len(r) and r[rpos]==i:\n",
    "                    rpos+=1\n",
    "                else:\n",
    "                    if s[i]==p[ppos]:\n",
    "                        ppos+=1\n",
    "                        if ppos==plen:\n",
    "                            return True\n",
    "            return False\n",
    "        \n",
    "        l,r = 0,r_len\n",
    "        ans = -1\n",
    "        while l<=r:\n",
    "            mid = (l+r)//2\n",
    "            if check(mid):\n",
    "                ans = mid\n",
    "                l = mid + 1\n",
    "            else:\n",
    "                r = mid - 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumRemovals(self, s: str, p: str, removable: List[int]) -> int:\n",
    "        left = -1\n",
    "        right = len(removable) + 1\n",
    "        def check(mid):\n",
    "            temp = list(s)\n",
    "            for i in range(mid):\n",
    "                temp[removable[i]] = \"\"\n",
    "            ss = \"\".join(temp)\n",
    "            id = 0\n",
    "            for i in ss:\n",
    "                if i == p[id]:\n",
    "                    id+=1\n",
    "                if id ==len(p):\n",
    "                    return True\n",
    "            return False\n",
    "    \n",
    "\n",
    "\n",
    "\n",
    "        while left + 1 < right:\n",
    "            mid = left + (right - left )//2\n",
    "            if check(mid):\n",
    "                left = mid\n",
    "            else:\n",
    "                right = mid\n",
    "        \n",
    "        return right - 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumRemovals(self, s: str, p: str, removable: List[int]) -> int:\n",
    "        ns = len(s)\n",
    "        np = len(p)\n",
    "\n",
    "        def check(k: int) -> bool:\n",
    "            state = [False] * ns\n",
    "            for i in range(k):\n",
    "                state[removable[i]] = True\n",
    "            j = 0\n",
    "            for i in range(ns):\n",
    "                if not state[i] and s[i] == p[j]:\n",
    "                    j += 1\n",
    "                    if j == np:\n",
    "                        return True\n",
    "            return False\n",
    "\n",
    "        left, right = 0, len(removable)\n",
    "        while left <= right:\n",
    "            mid = (left + right) // 2\n",
    "            if check(mid):\n",
    "                left = mid + 1\n",
    "            else:\n",
    "                right = mid - 1\n",
    "        return left - 1\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumRemovals(self, s: str, p: str, removable: List[int]) -> int:\n",
    "        l, r = 0, len(removable)\n",
    "        ls, lp = len(s), len(p)\n",
    "        def check(k):\n",
    "            state = [True] * ls\n",
    "            for i in range(k):\n",
    "                state[removable[i]] = False\n",
    "            pi = 0\n",
    "            si = 0\n",
    "            while si < ls:\n",
    "                if not state[si]:\n",
    "                    si += 1\n",
    "                    continue\n",
    "                if s[si] == p[pi]:\n",
    "                    pi += 1\n",
    "                si += 1\n",
    "                if pi == lp:\n",
    "                    return True\n",
    "            return False\n",
    "            \n",
    "\n",
    "        while l <= r:\n",
    "            mid = (l + r) // 2\n",
    "            if check(mid):\n",
    "                l = mid + 1\n",
    "            else:\n",
    "                r = mid - 1\n",
    "\n",
    "        return l - 1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumRemovals(self, s: str, p: str, removable: List[int]) -> int:\n",
    "\n",
    "        ns, np, n = len(s), len(p), len(removable)\n",
    "\n",
    "        def check(k):\n",
    "            state = [True] * ns\n",
    "            for idx in removable[:k+1]:\n",
    "                state[idx] = False\n",
    "            \n",
    "            j = 0\n",
    "            for i in range(ns):\n",
    "                if state[i] and s[i] == p[j]:\n",
    "                    j += 1\n",
    "                    if j == np:\n",
    "                        return True\n",
    "            return False\n",
    "        \n",
    "        # 从左到右找最后一个满足的\n",
    "        if not check(0):\n",
    "            return 0\n",
    "\n",
    "        l, r = 0, n-1\n",
    "        while l < r:\n",
    "            mid = l + r + 1 >> 1\n",
    "            if check(mid):\n",
    "                l = mid\n",
    "            else:\n",
    "                r = mid - 1\n",
    "        \n",
    "        return l + 1\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumRemovals(self, s: str, p: str, removable: List[int]) -> int:\n",
    "        l = 0\n",
    "        r = len(removable)\n",
    "        n = len(s)\n",
    "        def check(k):\n",
    "            vis = [False]*n\n",
    "            for i in range(k):\n",
    "                vis[removable[i]]=True\n",
    "            i = 0\n",
    "            j = 0\n",
    "            while i<len(p) and j<n:\n",
    "                if p[i]==s[j] and not vis[j]:\n",
    "                    i+=1\n",
    "                    j+=1\n",
    "                else:\n",
    "                    j+=1\n",
    "            if i==len(p):\n",
    "                return True\n",
    "            else:\n",
    "                return False\n",
    "        while l<r:\n",
    "            mid = l+r+1>>1\n",
    "            if check(mid):\n",
    "                l = mid\n",
    "            else:\n",
    "                r = mid-1\n",
    "        return l \n",
    "        \n",
    "                \n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumRemovals(self, s: str, p: str, removable: List[int]) -> int:\n",
    "        n = len(s)\n",
    "        m = len(p)\n",
    "        def check(k:int)->int:\n",
    "            t = sorted(removable[:k+1])\n",
    "            i = 0\n",
    "            cur = 0\n",
    "            for j in range(n):\n",
    "                if i<len(t) and j==t[i]:\n",
    "                    i+=1\n",
    "                    continue\n",
    "                if p[cur]==s[j]:\n",
    "                    cur+=1\n",
    "                if cur>=m:\n",
    "                    break\n",
    "            return cur>=m\n",
    "        l,r = 0, len(removable)\n",
    "        while l<r:\n",
    "            mid = l+(r-l)//2\n",
    "            if not check(mid):\n",
    "                r = mid\n",
    "            else:\n",
    "                l = mid+1\n",
    "        # for i in range(n):\n",
    "        #     print(check(i))\n",
    "        return l\n",
    "        # return bisect_right(removable,-m,key = check)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumRemovals(self, s: str, p: str, removable: List[int]) -> int:\n",
    "        n = len(s)\n",
    "        k = len(removable)\n",
    "        lenP = len(p)\n",
    "\n",
    "        left = 0\n",
    "        right = k - 1\n",
    "\n",
    "        while left <= right:\n",
    "            mid = (left + right) // 2\n",
    "\n",
    "            state = [True] * n\n",
    "\n",
    "            for i in range(mid + 1):\n",
    "                state[removable[i]] = False\n",
    "            pos = 0\n",
    "            condition = False\n",
    "            for i, ch in enumerate(s):\n",
    "                if not state[i]:\n",
    "                    continue\n",
    "                if ch == p[pos]:\n",
    "                    pos += 1\n",
    "                    if pos == lenP:\n",
    "                        condition = True\n",
    "                        break\n",
    "            \n",
    "            if condition:\n",
    "                left = mid + 1\n",
    "            else:\n",
    "                right = mid - 1\n",
    "        \n",
    "        return left"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumRemovals(self, s: str, p: str, removable: List[int]) -> int:\n",
    "        m, n = len(s), len(p)\n",
    "        left, right = 0, min(m - n, len(removable))\n",
    "        while left <= right:\n",
    "            mid = (left + right) // 2\n",
    "            def check(x: int) -> bool:\n",
    "                is_remove = [False] * m \n",
    "                for i in removable[ : x]:\n",
    "                    is_remove[i] = True\n",
    "                i = 0\n",
    "                for j in range(n):\n",
    "                    while i < m and (is_remove[i] or (not is_remove[i] and s[i] != p[j])):\n",
    "                        i += 1\n",
    "                    if i == m:\n",
    "                        return False\n",
    "                    i += 1\n",
    "                return True\n",
    "            if check(mid):\n",
    "                left = mid + 1\n",
    "            else:\n",
    "                right = mid - 1\n",
    "        return right"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumRemovals(self, s: str, p: str, removable: List[int]) -> int:\n",
    "\n",
    "\n",
    "        def check(k,s):\n",
    "\n",
    "            for i in range(k):\n",
    "                s[removable[i]] = ' '\n",
    "            s = ''.join(s).split(' ')\n",
    "            s = ''.join(s)\n",
    "  \n",
    "            ls ,n = 0, len(s)\n",
    "            for idx, pp in enumerate(p):\n",
    "                while ls < n and s[ls] != pp:\n",
    "                    ls += 1\n",
    "                if ls == n:\n",
    "                    return False\n",
    "                ls += 1 \n",
    "            return True\n",
    "\n",
    "        \n",
    "        left,right = 0,len(removable)\n",
    "        while left <= right:\n",
    "            mid = (left+right) >> 1\n",
    "            if check(mid,list(s)):\n",
    "                left = mid+1\n",
    "            else:\n",
    "                right = mid -1\n",
    "        return right"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumRemovals(self, s: str, p: str, removable: List[int]) -> int:\n",
    "        def check(k):\n",
    "            # 检测 k 是否符合要求\n",
    "            lis = [_ for _ in s]  # 转成列表方便赋值\n",
    "\n",
    "            for idx in removable[:k]:\n",
    "                lis[idx] = ''\n",
    "\n",
    "            # 检查是否p是s的子序列\n",
    "            i = 0\n",
    "            j = 0\n",
    "            cnt = 0\n",
    "            while j < len(p) and i < len(s):\n",
    "                while i < len(s) and p[j] != lis[i]:\n",
    "                    i += 1\n",
    "                if i == len(s): break\n",
    "                \n",
    "                if p[j] == lis[i]:\n",
    "                    cnt += 1\n",
    "                    i += 1\n",
    "                    j += 1\n",
    "                    \n",
    "            return  cnt == len(p)\n",
    "\n",
    "\n",
    "        left = -1\n",
    "        right = len(removable) + 1\n",
    "        while left + 1 < right:\n",
    "            mid = (left + right) // 2\n",
    "            if check(mid):\n",
    "                left = mid\n",
    "            else:\n",
    "                right = mid\n",
    "\n",
    "        return left"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumRemovals(self, s: str, p: str, removable: List[int]) -> int:\n",
    "        # 二分查找上限\n",
    "        left, right = 0, len(removable)\n",
    "        while left < right:\n",
    "            mid = left + (right - left + 1) // 2\n",
    "            if not self.is_valid(mid, removable, s, p):\n",
    "                right = mid - 1\n",
    "            else:\n",
    "                left = mid\n",
    "        return left\n",
    "\n",
    "    \n",
    "    def is_valid(self, mid, removable, s, p):\n",
    "        cache = set(removable[:mid])\n",
    "        s_size, p_size = len(s), len(p)\n",
    "        s_p, p_p = 0, 0\n",
    "        while s_p < s_size and p_p < p_size:\n",
    "            if s_p not in cache and s[s_p] == p[p_p]:\n",
    "                p_p += 1\n",
    "            s_p += 1\n",
    "            if p_p == p_size:\n",
    "                return True\n",
    "        return False\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "        \n",
    "    \n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "from typing import List\n",
    "from sortedcontainers import SortedSet\n",
    "from copy import deepcopy\n",
    "\n",
    "class Solution:\n",
    "    def maximumRemovals(self, s: str, p: str, removable: List[int]) -> int:\n",
    "        def valid(length):\n",
    "            pos = set(removable[:length])\n",
    "            i = 0\n",
    "            for j in range(len(s)):\n",
    "                if i == len(p):\n",
    "                    break\n",
    "\n",
    "                if j in pos:\n",
    "                    continue\n",
    "\n",
    "                if s[j] == p[i]:\n",
    "                    i += 1\n",
    "\n",
    "            return i == len(p)\n",
    "\n",
    "\n",
    "        l, r = 0, len(removable)\n",
    "        ans = 0\n",
    "        while l <= r:\n",
    "            mid = (l + r) // 2\n",
    "            if valid(mid):\n",
    "                ans = mid\n",
    "                l = mid + 1\n",
    "            else:\n",
    "                r = mid - 1\n",
    "\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumRemovals(self, s: str, p: str, removable: List[int]) -> int:\n",
    "        n = len(s)\n",
    "        slist = list(s)\n",
    "        def check(x,tmp_s):\n",
    "            for i in removable[:x]:\n",
    "                tmp_s[i] = '#'\n",
    "            l1, r1 = 0, len(tmp_s) - 1\n",
    "            l2, r2 = 0, len(p) - 1\n",
    "            while(l1 <= r1 and l2 <= r2):\n",
    "                if(tmp_s[l1] == p[l2]):\n",
    "                    l2 += 1\n",
    "                l1 += 1\n",
    "                if(l1 > r1):\n",
    "                    break\n",
    "                if(tmp_s[r1] == p[r2]):\n",
    "                    r2 -= 1\n",
    "                r1 -= 1\n",
    "            return l2 > r2\n",
    "        left, right = 0, len(removable)\n",
    "        while(left <= right):\n",
    "            mid = (left+right)//2\n",
    "            if(check(mid, slist[:])):\n",
    "                left = mid + 1\n",
    "            else:\n",
    "                right = mid - 1\n",
    "        return right"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumRemovals(self, s: str, p: str, removable: List[int]) -> int:\n",
    "        n = len(s)\n",
    "        slist = list(s)\n",
    "        def check(x,tmp_s):\n",
    "            for i in removable[:x]:\n",
    "                tmp_s[i] = '#'\n",
    "            l1, r1 = 0, len(tmp_s) - 1\n",
    "            l2, r2 = 0, len(p) - 1\n",
    "            while(l1 <= r1 and l2 <= r2):\n",
    "                if(tmp_s[l1] == p[l2]):\n",
    "                    l2 += 1\n",
    "                l1 += 1\n",
    "                if(l1 > r1):\n",
    "                    break\n",
    "                if(tmp_s[r1] == p[r2]):\n",
    "                    r2 -= 1\n",
    "                r1 -= 1\n",
    "            return l2 > r2\n",
    "        left, right = 0, len(removable)\n",
    "        while(left <= right):\n",
    "            mid = (left+right)//2\n",
    "            if(check(mid, slist[:])):\n",
    "                left = mid + 1\n",
    "            else:\n",
    "                right = mid - 1\n",
    "        return right"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumRemovals(self, s: str, p: str, removable: List[int]) -> int:\n",
    "        def check(mid: int) -> bool:\n",
    "            i=0\n",
    "            for c in s:\n",
    "                if c[0]==p[i]:\n",
    "                    i+=1\n",
    "                if i==m:\n",
    "                    break\n",
    "            return i==m\n",
    "\n",
    "        s=list(s)\n",
    "        n,m,k=len(s),len(p),len(removable)\n",
    "        l,r,last=0,k,0\n",
    "        while l<r:\n",
    "            mid=(l+r+1)//2\n",
    "            if mid>=last:\n",
    "                for i in range(last,mid):\n",
    "                    s[removable[i]]='0'+s[removable[i]]\n",
    "            else:\n",
    "                for i in range(mid,last):\n",
    "                    s[removable[i]]=s[removable[i]][1]\n",
    "            if check(mid):\n",
    "                l=mid\n",
    "            else:\n",
    "                r=mid-1\n",
    "            last=mid\n",
    "        return l\n",
    "\n",
    "\n",
    "'''\n",
    "法一 二分查找\n",
    "二分查找0~len(removable)，\n",
    "check时，先生成删掉这些字符的字符串，时间复杂度O(k)，k表示折半查找的index\n",
    "然后执行双指针匹配算法时间复杂度O(len(s))，综合来讲时间复杂度O(len(s))因为len(s)>k\n",
    "\n",
    "综上 \n",
    "时间复杂度O(len(s)*logn)，n表示removable长度，也可以认为极限时O(len(s)*log(len(s)))\n",
    "空间复杂度O(len(p))\n",
    "'''"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumRemovals(self, s: str, p: str, removable: List[int]) -> int:\n",
    "        def check(mid: int) -> bool:\n",
    "            for i in range(mid):\n",
    "                s[removable[i]]='0'+s[removable[i]]\n",
    "            i=0\n",
    "            for c in s:\n",
    "                if c[0]==p[i]:\n",
    "                    i+=1\n",
    "                if i==m:\n",
    "                    break\n",
    "            for j in range(mid):\n",
    "                s[removable[j]]=s[removable[j]][1]\n",
    "            return i==m\n",
    "\n",
    "        s=list(s)\n",
    "        n,m,k=len(s),len(p),len(removable)\n",
    "        l,r=0,k\n",
    "        while l<r:\n",
    "            mid=(l+r+1)//2\n",
    "            if check(mid):\n",
    "                l=mid\n",
    "            else:\n",
    "                r=mid-1\n",
    "        return l\n",
    "\n",
    "\n",
    "'''\n",
    "法一 二分查找\n",
    "二分查找0~len(removable)，\n",
    "check时，先生成删掉这些字符的字符串，时间复杂度O(k)，k表示折半查找的index\n",
    "然后执行双指针匹配算法时间复杂度O(len(s))，综合来讲时间复杂度O(len(s))因为len(s)>k\n",
    "\n",
    "综上 \n",
    "时间复杂度O(len(s)*logn)，n表示removable长度，也可以认为极限时O(len(s)*log(len(s)))\n",
    "空间复杂度O(len(p))\n",
    "'''"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumRemovals(self, s: str, p: str, removable: List[int]) -> int:\n",
    "        def isSubsequence(n) -> bool:\n",
    "            removed = set()\n",
    "            for i in range(n):\n",
    "                removed.add(removable[i])\n",
    "            ls1,ls2 = 0,0\n",
    "\n",
    "            l1,l2 = len(s),len(p)\n",
    "            if l1==0:\n",
    "                return True\n",
    "            while ls1<l1 and ls2<l2:\n",
    "                if ls1 not in removed:\n",
    "                    if p[ls2]==s[ls1]:\n",
    "                        ls1+=1\n",
    "                        ls2+=1\n",
    "                    else:\n",
    "                        ls1+=1\n",
    "                else:\n",
    "                    ls1+=1\n",
    "            return ls2==l2\n",
    "        lo = 0\n",
    "        hi = len(removable)\n",
    "        mid = (lo+hi)//2\n",
    "        while lo<hi:\n",
    "            mid = (lo+hi)//2\n",
    "            if isSubsequence(mid):\n",
    "                lo = mid\n",
    "                mid = (lo+hi)//2\n",
    "            else:\n",
    "                hi = mid-1\n",
    "                mid = (lo+hi)//2\n",
    "            if lo==hi-1:\n",
    "                if isSubsequence(hi):\n",
    "                    return hi\n",
    "                else:\n",
    "                    return lo\n",
    "        return lo"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumRemovals(self, s: str, p: str, removable: List[int]) -> int:\n",
    "        def is_sub(s: str, t: str, no_use) -> bool:\n",
    "            n, m = len(s), len(t)\n",
    "            i = j = 0\n",
    "            while i < n and j < m:\n",
    "                if j in no_use:\n",
    "                    j += 1\n",
    "                    continue\n",
    "                if s[i] == t[j]:\n",
    "                    i += 1\n",
    "                j += 1\n",
    "            return i == n\n",
    "        \n",
    "        def check(mid):\n",
    "            remove = set([i for i in removable[:mid]])\n",
    "            return is_sub(p, s, remove)\n",
    "        l = 0\n",
    "        r = len(removable)\n",
    "        while l<r:\n",
    "            mid = (l+r+1)>>1\n",
    "            if check(mid):\n",
    "                l = mid\n",
    "            else:\n",
    "                r = mid-1\n",
    "        return l"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumRemovals(self, s: str, p: str, removable: List[int]) -> int:\n",
    "        def can_remove(k):\n",
    "            sids2remove = set(removable[:k])\n",
    "            new_s = \"\"\n",
    "            for i, c in enumerate(s):\n",
    "                if i not in sids2remove:\n",
    "                    new_s += c\n",
    "            return is_sub(p, new_s)\n",
    "\n",
    "\n",
    "        def is_sub(s, l): # O(n)\n",
    "            nl, ns = len(l), len(s)\n",
    "            if nl < ns:\n",
    "                return False\n",
    "            li = si = 0\n",
    "            while si < ns:\n",
    "                while li < nl and l[li] != s[si]:\n",
    "                    li += 1\n",
    "                if li == nl:\n",
    "                    return False\n",
    "                li += 1\n",
    "                si += 1\n",
    "            return True\n",
    "\n",
    "        l, r = -1, len(removable) + 1\n",
    "        while r - l > 1:\n",
    "            m = l + r >> 1\n",
    "            if can_remove(m):\n",
    "                l = m \n",
    "            else:\n",
    "                r = m \n",
    "        return l"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumRemovals(self, s: str, p: str, removable: List[int]) -> int:\n",
    "        def is_substr(k):\n",
    "            ss=set(removable[:k])\n",
    "            pi=0\n",
    "            for i in range(len(s)):\n",
    "                if i in ss:\n",
    "                    continue\n",
    "                if s[i]==p[pi]:\n",
    "                    pi+=1\n",
    "                    if pi==len(p):\n",
    "                        return True\n",
    "            return False\n",
    "            \n",
    "        left,right=0,len(removable)\n",
    "        while left<=right:\n",
    "            mid=(left+right)//2\n",
    "            if is_substr(mid):\n",
    "                left=mid+1\n",
    "            else:\n",
    "                right=mid-1\n",
    "        return right"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def maximumRemovals(self, s: str, p: str, removable: List[int]) -> int:\n",
    "        n, m = len(removable), len(s)\n",
    "        left, right = 0, n - 1\n",
    "        res = 0\n",
    "        while left <= right:\n",
    "            mid = left + (right - left) // 2\n",
    "            k_removeable = sorted(removable[:mid + 1])\n",
    "            j = 0\n",
    "            st = ''\n",
    "            for i in range(m):\n",
    "                if j < mid + 1 and i == k_removeable[j]:\n",
    "                    j += 1\n",
    "                    continue\n",
    "                st += s[i]\n",
    "            if self.is_substring(st, p):\n",
    "                res = max(res, mid + 1)\n",
    "                left = mid + 1\n",
    "            else:\n",
    "                right = mid - 1\n",
    "        return res\n",
    "\n",
    "    def is_substring(self, a, b):\n",
    "        i, j = 0, 0\n",
    "        while i < len(a) and j < len(b):\n",
    "\n",
    "            if a[i] == b[j]:\n",
    "                j += 1\n",
    "            i += 1\n",
    "        return j == len(b)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumRemovals(self, s: str, p: str, removable: List[int]) -> int:\n",
    "        def exists(t, s, mid):\n",
    "            se = set(removable[:mid + 1])\n",
    "            n, m = len(s), len(t)\n",
    "            i = j = 0\n",
    "            while i < n and j < m:\n",
    "                if j not in se and s[i] == t[j]:\n",
    "                    i += 1\n",
    "                j += 1\n",
    "            return i == n\n",
    "        \n",
    "        low, high = 0, len(removable)\n",
    "        while low < high:\n",
    "            mid = (low + high) // 2\n",
    "            if exists(s, p, mid):\n",
    "                low = mid + 1\n",
    "            else:\n",
    "                high = mid\n",
    "        return low\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumRemovals(self, s: str, p: str, removable: List[int]) -> int:\n",
    "        #二分，当移除前k个下标能满足p仍是移除后的s的子序列，那么最大的k一定在[k,n]中\n",
    "        ns,np=len(s),len(p)\n",
    "        def isOk(k):\n",
    "            delete = set(removable[:k])\n",
    "            i_s = i_p = 0\n",
    "\n",
    "            while i_s<ns and i_p<np:\n",
    "                if i_s not in delete and s[i_s] == p[i_p]:\n",
    "                    i_p += 1\n",
    "                i_s += 1\n",
    "            return i_p == np\n",
    "\n",
    "\n",
    "\n",
    "        l,r = 0,len(removable)\n",
    "        while l < r:\n",
    "            mid = (l+r+1)//2\n",
    "            if isOk(mid):\n",
    "                l = mid\n",
    "            else:\n",
    "                r = mid - 1\n",
    "        return l"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumRemovals(self, s: str, p: str, removable: List[int]) -> int:\n",
    "        #二分，当移除前k个下标能满足p仍是移除后的s的子序列，那么最大的k一定在[k,n]中\n",
    "\n",
    "        def isOk(k):\n",
    "            delete = set(removable[:k])\n",
    "            i_s = i_p = 0\n",
    "            ns,np=len(s),len(p)\n",
    "\n",
    "            while i_s<ns and i_p<np:\n",
    "                if i_s in delete:\n",
    "                    i_s += 1\n",
    "                    continue\n",
    "                if s[i_s] == p[i_p]:\n",
    "                    i_p += 1\n",
    "                i_s += 1\n",
    "            return i_p == np\n",
    "\n",
    "\n",
    "\n",
    "        l,r = 0,len(removable)\n",
    "        while l < r:\n",
    "            mid = (l+r+1)//2\n",
    "            if isOk(mid):\n",
    "                l = mid\n",
    "            else:\n",
    "                r = mid - 1\n",
    "        return l"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumRemovals(self, s: str, p: str, removable: List[int]) -> int:\n",
    "        #二分，当移除前k个下标能满足p仍是移除后的s的子序列，那么最大的k一定在[k,n]中\n",
    "\n",
    "        def isOk(k):\n",
    "            delete = set(removable[:k])\n",
    "            i_s = i_p = 0\n",
    "            ns,np=len(s),len(p)\n",
    "\n",
    "            while i_s<ns and i_p<np:\n",
    "                i_s += 1\n",
    "                if i_s-1 in delete:\n",
    "                    continue\n",
    "                if s[i_s-1] == p[i_p]:\n",
    "                    i_p += 1\n",
    "            return i_p == np\n",
    "\n",
    "\n",
    "\n",
    "        l,r = 0,len(removable)\n",
    "        while l < r:\n",
    "            mid = (l+r+1)//2\n",
    "            if isOk(mid):\n",
    "                l = mid\n",
    "            else:\n",
    "                r = mid - 1\n",
    "        return l"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "      def maximumRemovals(self, s: str, p: str, removable: List[int]) -> int:\n",
    "        left, right = 0, len(removable)\n",
    "        ans = 0\n",
    "\n",
    "        def isSubStr(k: int) -> bool:\n",
    "            removeSet = set()\n",
    "            for i in range(k):\n",
    "                removeSet.add(removable[i])\n",
    "            i, j = 0, 0\n",
    "            while i < len(s) and j < len(p):\n",
    "                if i not in removeSet and s[i] == p[j]:\n",
    "                    j += 1\n",
    "                i += 1\n",
    "            return j == len(p)\n",
    "        while left <= right:\n",
    "            mid = left+(right-left)//2\n",
    "            if isSubStr(mid):\n",
    "                ans = mid\n",
    "                left = mid+1\n",
    "            else:\n",
    "                right = mid-1\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def maximumRemovals(self, s: str, p: str, removable: list[int]) -> int:\r\n",
    "        len_s, len_p = len(s), len(p)\r\n",
    "\r\n",
    "        def check(k):\r\n",
    "            i = j = 0\r\n",
    "            ids = set(removable[:k])\r\n",
    "            while i < len_s and j < len_p:\r\n",
    "                if i not in ids and s[i] == p[j]:\r\n",
    "                    j += 1\r\n",
    "                i += 1\r\n",
    "            return j == len_p\r\n",
    "\r\n",
    "        left, right = 0, len(removable)\r\n",
    "        while left < right:\r\n",
    "            mid = (left + right + 1) >> 1 # 防止left比right小1，mid一直等于left进行死循环\r\n",
    "            if check(mid):\r\n",
    "                left = mid\r\n",
    "            else:\r\n",
    "                right = mid - 1\r\n",
    "\r\n",
    "        return left\r\n",
    "\r\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumRemovals(self, s: str, p: str, removable: List[int]) -> int:      \n",
    "      m,n=len(s),len(p)\n",
    "      def check(k):\n",
    "        i,j=0,0\n",
    "        check_list=set(removable[:k])\n",
    "        while i<m and j<n:\n",
    "          if i not in check_list and s[i] == p[j]:\n",
    "            j+=1\n",
    "          i+=1\n",
    "        return j == n\n",
    "      left,right=0,len(removable)\n",
    "      while left<right:\n",
    "        mid=(left+right+1)>>1\n",
    "        if check(mid):\n",
    "          left=mid\n",
    "        else:\n",
    "          right=mid-1\n",
    "      return left\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumRemovals(self, s: str, p: str, removable: list[int]) -> int:\n",
    "        def ck(x):\n",
    "            x += 1\n",
    "            st = set(removable[:x])\n",
    "            i, n = 0, len(s)\n",
    "            for ch in p:\n",
    "                while i < n and (i in st or s[i] != ch):\n",
    "                    i += 1\n",
    "                if i == n:\n",
    "                    return True\n",
    "                i += 1\n",
    "            return False\n",
    "\n",
    "        return bisect_left(range(len(removable)), True, key=ck)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def is_substr(self, s: str, p: str, a: List[int]) -> bool:\n",
    "        remove = set(a)\n",
    "        j = 0\n",
    "        for i in range(len(s)):\n",
    "            if i in remove:\n",
    "                continue\n",
    "            if j == len(p):\n",
    "                break\n",
    "            if s[i] == p[j]:\n",
    "                j += 1\n",
    "        return j == len(p)\n",
    "\n",
    "    def maximumRemovals(self, s: str, p: str, removable: List[int]) -> int:\n",
    "        left = 0\n",
    "        right = len(removable)\n",
    "        while left < right:\n",
    "            mid = (left + right) //2\n",
    "            if self.is_substr(s, p, removable[:mid]):\n",
    "                left = mid + 1\n",
    "            else:\n",
    "                right = mid\n",
    "        return left if self.is_substr(s, p, removable[:left]) else left - 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumRemovals(self, s: str, p: str, removable: List[int]) -> int:\n",
    "        def check(mid):\n",
    "            new_removable = set(removable[:mid+1])\n",
    "            new_s = \"\"\n",
    "            for i in range(len(s)):\n",
    "                if i not in new_removable:\n",
    "                    new_s += s[i]\n",
    "            \n",
    "            l, r = 0, 0\n",
    "            while l < len(new_s):\n",
    "                if new_s[l] == p[r]:\n",
    "                    r += 1\n",
    "                if r == len(p):\n",
    "                    break\n",
    "                l += 1\n",
    "            return r == len(p)\n",
    "        \n",
    "        l, r = -1, len(removable)\n",
    "        while l + 1 < r:\n",
    "            mid = l + (r - l) // 2\n",
    "            if check(mid):\n",
    "                l = mid\n",
    "            else:\n",
    "                r = mid\n",
    "        print(check(r))\n",
    "        return l+1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumRemovals(self, s: str, p: str, removable: List[int]) -> int:\n",
    "        p_length = len(p)\n",
    "        def check(mid):\n",
    "            new_removable = set(removable[:mid+1])\n",
    "            new_s = \"\"\n",
    "            for i in range(len(s)):\n",
    "                if i not in new_removable:\n",
    "                    new_s += s[i]\n",
    "\n",
    "            l, r = 0, 0\n",
    "            while l < len(new_s) and r < p_length:\n",
    "                if new_s[l] == p[r]:\n",
    "                    l += 1\n",
    "                    r += 1\n",
    "                else:\n",
    "                    l += 1\n",
    "            return r == len(p)\n",
    " \n",
    "        \n",
    "        l, r = -1, len(removable)\n",
    "        while l + 1 < r:\n",
    "            mid = l + (r - l) // 2\n",
    "            if check(mid):\n",
    "                l = mid\n",
    "            else:\n",
    "                r = mid\n",
    "        return l+1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumRemovals(self, s: str, p: str, removable: List[int]) -> int:\n",
    "        def exist(p, s, mid):\n",
    "            re = set(removable[:mid+1])\n",
    "            m, n = len(p), len(s)\n",
    "            i, j = 0, 0\n",
    "            while i < m and j < n:\n",
    "                if j not in re and p[i] == s[j]:\n",
    "                    i += 1\n",
    "                j += 1\n",
    "            return i == m\n",
    "        \n",
    "        left, right = 0, len(removable)\n",
    "        while left < right:\n",
    "            mid = (left + right) >> 1\n",
    "            if exist(p, s, mid):\n",
    "                left = mid + 1\n",
    "            else:\n",
    "                right = mid\n",
    "        return right"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumRemovals(self, s: str, p: str, removable: List[int]) -> int:\n",
    "        def check(x):\n",
    "            nonlocal n, m\n",
    "            vis = set()\n",
    "            for i in range(x + 1):\n",
    "                vis.add(removable[i])\n",
    "            r = 0\n",
    "            for l in range(n):\n",
    "                if p[r] == s[l] and l not in vis:\n",
    "                    r += 1\n",
    "                if r == m:\n",
    "                    return True\n",
    "            return False\n",
    "\n",
    "        n, m = len(s), len(p)\n",
    "        left, right = 0, len(removable)\n",
    "        while left < right:\n",
    "            mid = left + right >> 1\n",
    "            if check(mid):\n",
    "                left = mid + 1\n",
    "            else:\n",
    "                right = mid\n",
    "        return left"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumRemovals(self, s: str, p: str, removable: List[int]) -> int:\n",
    "        def check(word,sub):  #检验sub是否为子串\n",
    "            n=len(sub)\n",
    "            i=0\n",
    "            while i<n:\n",
    "                if sub[i] not in word:\n",
    "                    return False\n",
    "                t=word.index(sub[i])\n",
    "                word=word[t+1:]\n",
    "                i+=1\n",
    "            return True\n",
    "        def revise(word,lst):\n",
    "            s=''\n",
    "            n=len(word)\n",
    "            for i in range(n):\n",
    "                if i not in lst:\n",
    "                    s+=word[i]\n",
    "            return s\n",
    "        cmin=0\n",
    "        cmax=len(removable)\n",
    "        while cmin<=cmax:\n",
    "            mid=(cmin+cmax)//2\n",
    "            lst_revise=removable[:mid]\n",
    "            revised_word=revise(s,set(lst_revise))\n",
    "            if check(revised_word,p):\n",
    "                cur=mid\n",
    "                cmin=mid+1\n",
    "            else:\n",
    "                cmax=mid-1\n",
    "        return cur\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumRemovals(self, s: str, p: str, removable: List[int]) -> int:\n",
    "        n, m = len(s), len(p)\n",
    "        def check(s, p, abandon):\n",
    "            j = 0\n",
    "            for i in range(n):\n",
    "                if i in abandon:\n",
    "                    continue\n",
    "                if s[i] == p[j]:\n",
    "                    j += 1\n",
    "                    if j == m:\n",
    "                        return True\n",
    "            return False\n",
    "        \n",
    "        i, j = 0, len(removable)\n",
    "        mid = (i + j + 1) >> 1\n",
    "        abandon = set(removable[:mid])\n",
    "        while i < j:\n",
    "            if check(s, p, abandon):\n",
    "                i = mid\n",
    "                mid = (i + j + 1) >> 1\n",
    "                abandon |= set(removable[i:mid])\n",
    "            else:\n",
    "                j = mid - 1\n",
    "                mid = (i + j + 1) >> 1\n",
    "                abandon -= set(removable[mid:j+1])\n",
    "        return i"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumRemovals(self, s: str, p: str, removable: List[int]) -> int:\n",
    "        lo = 0\n",
    "        hi = len(removable)\n",
    "        ans = 0\n",
    "        def check(k):\n",
    "            rem = {e for e in removable[:k]}\n",
    "            j = 0\n",
    "            for i in range(len(s)):\n",
    "                if s[i] == p[j] and i not in rem:\n",
    "                    j+=1\n",
    "                if j == len(p):\n",
    "                    return True\n",
    "            return False\n",
    "        while lo<=hi:\n",
    "            mid = (lo+hi)//2\n",
    "            if check(mid):\n",
    "                ans = mid\n",
    "                lo = mid+1\n",
    "            else:\n",
    "                hi = mid - 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumRemovals(self, s: str, p: str, removable: List[int]) -> int:\n",
    "        \"\"\"可移除字符的最大数目\n",
    "        1. 二分查找\n",
    "        \"\"\"\n",
    "        def is_valid(x):\n",
    "            rm_set = set(removable[:x])\n",
    "            i, j = 0, 0\n",
    "            while i < len(s) and j < len(p):\n",
    "                if i in rm_set:\n",
    "                    i += 1\n",
    "                    continue\n",
    "                if s[i] == p[j]:\n",
    "                    j += 1\n",
    "                i += 1\n",
    "            return j == len(p)\n",
    "\n",
    "        l, r = 0, len(removable)\n",
    "        while l <= r:\n",
    "            mid = (l + r) // 2\n",
    "            if is_valid(mid):\n",
    "                l = mid + 1\n",
    "            else:\n",
    "                r = mid - 1\n",
    "        # f(l-1) = True\n",
    "        return l-1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumRemovals(self, s: str, p: str, removable: List[int]) -> int:\n",
    "        lo = 0\n",
    "        hi = len(removable)\n",
    "        ans = 0\n",
    "        def check(k):\n",
    "            rem = {e for e in removable[:k]}\n",
    "            i,j = 0,0\n",
    "            while i<len(s) and j<len(p):\n",
    "                if s[i] == p[j] and i not in rem:\n",
    "                    i+=1\n",
    "                    j+=1\n",
    "                else:\n",
    "                    i+=1\n",
    "            if j!=len(p):\n",
    "                return False\n",
    "            return True\n",
    "        while lo<=hi:\n",
    "            mid = (lo+hi)//2\n",
    "            if check(mid):\n",
    "                ans = mid\n",
    "                lo = mid+1\n",
    "            else:\n",
    "                hi = mid - 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumRemovals(self, s: str, p: str, removable: List[int]) -> int:\n",
    "        # 随着k越大，p会从是s的子序列变成不是s的子序列，所以可以用二分\n",
    "        # 蓝色区域为p是s的子序列，最后返回left\n",
    "        # 取值区间很明显是[0, len(removable)]\n",
    "        left, right = -1, len(removable)+1\n",
    "        while left+1 < right:\n",
    "            mid = (left+right) >> 1\n",
    "            if self.isSubSequence(s, p, set(removable[:mid])):\n",
    "                left = mid\n",
    "            else:\n",
    "                right = mid\n",
    "        return left\n",
    "\n",
    "    def isSubSequence(self, a, b, k):\n",
    "        # 判断b是否是a的子序列, 其中a不能去数组k中的下标   为了降低复杂度，k我们定义为一个集合\n",
    "        i = 0\n",
    "        for j in range(len(a)):\n",
    "            if j in k:\n",
    "                continue\n",
    "            if i < len(b) and a[j] == b[i]:\n",
    "                i += 1\n",
    "                if i == len(b): return True\n",
    "        return i == len(b)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumRemovals(self, s: str, p: str, removable: List[int]) -> int:\n",
    "        lo = 0\n",
    "        hi = len(removable)\n",
    "        ans = 0\n",
    "        def check(k):\n",
    "            rem = {e for e in removable[:k]}\n",
    "            i,j = 0,0\n",
    "            for i in range(len(s)):\n",
    "\n",
    "                if s[i] == p[j] and i not in rem:\n",
    "                    j+=1\n",
    "                if j == len(p):\n",
    "                    return True\n",
    "            return False\n",
    "        while lo<=hi:\n",
    "            mid = (lo+hi)//2\n",
    "            if check(mid):\n",
    "                ans = mid\n",
    "                lo = mid+1\n",
    "            else:\n",
    "                hi = mid - 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumRemovals(self, s: str, p: str, removable: List[int]) -> int:\n",
    "\n",
    "        left = 0\n",
    "        right = len(removable)\n",
    "\n",
    "        len_s , len_p = len(s),len(p)\n",
    "\n",
    "        def check(k)->bool:\n",
    "            nonlocal len_s,len_p\n",
    "            delete_indexs = set(removable[:k])\n",
    "            index1 = index2 = 0\n",
    "            while index1<len_s and index2<len_p:\n",
    "                if index1 in delete_indexs:\n",
    "                    index1+=1\n",
    "                    continue\n",
    "                if s[index1] == p[index2]:\n",
    "                    index1+=1\n",
    "                    index2+=1\n",
    "                else:\n",
    "                    index1+=1\n",
    "            \n",
    "            return index2 == len_p\n",
    "        \n",
    "        while left<right:\n",
    "            mid = left + (right - left+1)//2\n",
    "            if check(mid):\n",
    "                left = mid\n",
    "            else:\n",
    "                right = mid - 1\n",
    "        \n",
    "        return left"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumRemovals(self, s: str, p: str, removable: List[int]) -> int:\n",
    "        def judge(s, p):\n",
    "            i = j = 0\n",
    "            while i < len(s) and j < len(p):\n",
    "                if p[j] == s[i]:\n",
    "                    i += 1\n",
    "                    j += 1\n",
    "                else:\n",
    "                    i += 1\n",
    "            return j == len(p)\n",
    "        \n",
    "        l, r = 0, len(removable)\n",
    "        while l < r:\n",
    "            mid = l + r + 1 >> 1\n",
    "            new_removable = removable[:mid]\n",
    "            new_removable = set(new_removable)\n",
    "            new_s = ''\n",
    "            for i in range(len(s)):\n",
    "                if i not in new_removable:\n",
    "                    new_s += s[i]\n",
    "            if judge(new_s, p):\n",
    "                l = mid\n",
    "            else:\n",
    "                r = mid - 1\n",
    "        return l\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumRemovals(self, s: str, p: str, removable: List[int]) -> int:\n",
    "        def check(k):\n",
    "            removed = set(removable[:k])\n",
    "            j = 0\n",
    "            for i in range(len(s)):\n",
    "                if i in removed:\n",
    "                    continue\n",
    "                if j < len(p) and s[i] == p[j]:\n",
    "                    j += 1\n",
    "            return j == len(p)\n",
    "\n",
    "        l = 0\n",
    "        r = len(removable) + 1\n",
    "        while l < r:\n",
    "            m = (l + r) >> 1\n",
    "            if check(m):\n",
    "                l = m + 1\n",
    "            else:\n",
    "                r = m  \n",
    "        return l - 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumRemovals(self, s: str, p: str, removable: List[int]) -> int:\n",
    "        sz = len(removable)\n",
    "\n",
    "        def check(mid):\n",
    "            t = ''\n",
    "            st = set()\n",
    "            for i in range(mid):\n",
    "                st.add(removable[i])\n",
    "            for i in range(len(s)):\n",
    "                if i in st: continue\n",
    "                t += s[i]\n",
    "            n = len(p)\n",
    "            j = 0\n",
    "            for i in range(len(t)):\n",
    "                if t[i] == p[j]:\n",
    "                    j += 1\n",
    "                    if j == n:\n",
    "                        return True\n",
    "            return False\n",
    "\n",
    "        l = 0\n",
    "        r = len(removable)\n",
    "        while l < r:\n",
    "            mid = l + r + 1 >> 1\n",
    "            if check(mid): l = mid\n",
    "            else: r = mid - 1\n",
    "        return r"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumRemovals(self, s: str, p: str, removable: List[int]) -> int:\n",
    "        def check(k):\n",
    "            i = j = 0\n",
    "            ids = set(removable[:k])\n",
    "            while i < m and j < n:\n",
    "                if i not in ids and s[i] == p[j]:\n",
    "                    j += 1\n",
    "                i += 1\n",
    "            return j == n\n",
    "\n",
    "        m, n = len(s), len(p)\n",
    "        left, right = 0, len(removable)\n",
    "        while left < right:\n",
    "            mid = (left + right + 1) >> 1\n",
    "            if check(mid):\n",
    "                left = mid\n",
    "            else:\n",
    "                right = mid - 1\n",
    "        return left"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumRemovals(self, s: str, p: str, removable: List[int]) -> int:\n",
    "        def check(k):\n",
    "            i = j = 0\n",
    "            ids = set(removable[:k])\n",
    "            while i < len(s) and j < len(p):\n",
    "                if i not in ids and s[i] == p[j]:\n",
    "                    j += 1\n",
    "                i += 1\n",
    "            return j == len(p)\n",
    "\n",
    "        l, r = 0, len(removable)\n",
    "        while l < r:\n",
    "            mid = (l + r + 1) // 2\n",
    "            if check(mid):\n",
    "                l = mid\n",
    "            else:\n",
    "                r = mid - 1\n",
    "        return l\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumRemovals(self, s: str, p: str, removable: List[int]) -> int:\n",
    "        left, right, m, n = 0, len(removable), len(s), len(p)\n",
    "\n",
    "        def check(mid: int) -> bool:\n",
    "            states, i, j = set(removable[:mid + 1]), -1, 0\n",
    "            while (i := i + 1) < m:\n",
    "                if i not in states and s[i] == p[j]:\n",
    "                    j += 1\n",
    "                if j == n:\n",
    "                    return True\n",
    "            return False\n",
    "        while left < right:\n",
    "            if check(mid := left + ((right - left) >> 1)):\n",
    "                left = mid + 1\n",
    "            else:\n",
    "                right = mid\n",
    "        return left"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumRemovals(self, s: str, p: str, removable: List[int]) -> int:\n",
    "        m, n = len(s), len(p)\n",
    "        def check(x: int):\n",
    "            st = set(removable[0: x])\n",
    "            i, j = 0, 0\n",
    "            while i < m and j < n:\n",
    "                if i in st:\n",
    "                    i += 1\n",
    "                    continue\n",
    "                if s[i] == p[j]:\n",
    "                    j += 1\n",
    "                i += 1\n",
    "            return j == n\n",
    "         \n",
    "        l, r = -1, len(removable) + 1\n",
    "        while l + 1 < r:\n",
    "            mid = l + (r - l) // 2\n",
    "            if check(mid):\n",
    "                l = mid\n",
    "            else:\n",
    "                r = mid\n",
    "        return l"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumRemovals(self, s: str, p: str, removable: List[int]) -> int:\n",
    "        def check(k):\n",
    "            i = j = 0\n",
    "            ids = set(removable[:k])\n",
    "            while i < m and j < n:\n",
    "                if i not in ids and s[i] == p[j]:\n",
    "                    j += 1\n",
    "                i += 1\n",
    "            return j == n\n",
    "\n",
    "        m, n = len(s), len(p)\n",
    "        left, right = 0, len(removable)\n",
    "        while left < right:\n",
    "            mid = (left + right + 1) >> 1\n",
    "            if check(mid):\n",
    "                left = mid\n",
    "            else:\n",
    "                right = mid - 1\n",
    "        return left"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumRemovals(self, s: str, p: str, removable: List[int]) -> int:\n",
    "\n",
    "        def is_subsequence(s, p): \n",
    "            i = j = 0 \n",
    "            m, n = len(s), len(p) \n",
    "            while i < m and j < n: \n",
    "                if s[i] == p[j]: j += 1 \n",
    "                i += 1 \n",
    "            return j == n\n",
    "\n",
    "        def ck(x): \n",
    "            st = set(removable[:x])\n",
    "            ss = \"\"\n",
    "            for i, cc in enumerate(s):\n",
    "                if i not in st:\n",
    "                    ss += cc \n",
    "            return is_subsequence(ss, p)\n",
    "\n",
    "        l, r = 0, len(removable)\n",
    "        while l < r:\n",
    "            mid = l + r + 1 >> 1\n",
    "            if ck(mid): l = mid \n",
    "            else: r = mid - 1 \n",
    "        return l "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumRemovals(self, s: str, p: str, removable: List[int]) -> int:\n",
    "        # 二分答案即可\n",
    "        l,r=0,len(removable)\n",
    "        def check(m):\n",
    "            drop=set(removable[:m])\n",
    "            tmps=[c for i,c in enumerate(s) if i not in drop]\n",
    "            lengths,lengthp=len(tmps),len(p)\n",
    "            i,j=0,0\n",
    "            while i<lengths and j<lengthp:\n",
    "                if tmps[i]==p[j]:\n",
    "                    j+=1\n",
    "                i+=1\n",
    "            return j==lengthp\n",
    "        while l<r:\n",
    "            m=l+r+1>>1\n",
    "            if check(m):\n",
    "                l=m \n",
    "            else:\n",
    "                r=m-1\n",
    "        return l\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumRemovals(self, s: str, p: str, removable: List[int]) -> int:\n",
    "\n",
    "        def is_subsequence(s, p): \n",
    "            i = j = 0 \n",
    "            m, n = len(s), len(p) \n",
    "            while i < m and j < n: \n",
    "                if s[i] == p[j]: j += 1 \n",
    "                i += 1 \n",
    "            return j == n\n",
    "\n",
    "        def ck(x): \n",
    "            st = set(removable[:x])\n",
    "            ss = \"\"\n",
    "            for i, cc in enumerate(s):\n",
    "                if i not in st:\n",
    "                    ss += cc \n",
    "            return is_subsequence(ss, p)\n",
    "\n",
    "        l, r = 0, len(removable)\n",
    "        while l < r:\n",
    "            mid = l + r + 1 >> 1\n",
    "            if ck(mid): l = mid \n",
    "            else: r = mid - 1 \n",
    "        return l "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumRemovals(self, s: str, p: str, removable: List[int]) -> int:\n",
    "        left, right = -1, len(removable) + 1\n",
    "        while left + 1 < right:\n",
    "            mid = left + right >> 1\n",
    "            re = set(removable[:mid])\n",
    "            j = 0\n",
    "            for i in range(len(s)):\n",
    "                if s[i] == p[j] and i not in re:\n",
    "                    j += 1\n",
    "                    if len(p) == j:\n",
    "                        break\n",
    "            if len(p) == j:\n",
    "                left = mid\n",
    "            else:\n",
    "                right = mid\n",
    "        return left"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumRemovals(self, s: str, p: str, removable: List[int]) -> int:\n",
    "        n = len(s)\n",
    "\n",
    "        def check(mid):\n",
    "            re = set(removable[:mid])\n",
    "            ss = [ch for i, ch in enumerate(s) if i not in re]\n",
    "            x = iter(ss)\n",
    "            return all(ch in x for ch in p)\n",
    "\n",
    "        l, r = 1, len(removable)\n",
    "        return bisect_left(range(r + 1), 1, l, key=lambda t: not check(t)) - 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumRemovals(self, s: str, p: str, removable: List[int]) -> int:\n",
    "        def issub(s,p):\n",
    "            i1,i2 = 0, 0\n",
    "            while i1<len(s) and i2<len(p):\n",
    "                if i1 in removed or s[i1]!=p[i2]:\n",
    "                    i1+=1\n",
    "                else:\n",
    "                    i1+=1\n",
    "                    i2+=1\n",
    "                if i2==len(p):\n",
    "                    return True\n",
    "            return False\n",
    "        res=0\n",
    "        l,r=0,len(removable)-1\n",
    "        while l<=r:\n",
    "            m = (l+r)//2\n",
    "            removed = set(removable[:m+1])\n",
    "            if issub(s,p):\n",
    "                res = max(res,m+1)\n",
    "                l=m+1\n",
    "            else:\n",
    "                r=m-1\n",
    "        return res\n",
    "                \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumRemovals(self, s: str, p: str, removable: List[int]) -> int:\n",
    "        res = 0\n",
    "        left, right = 0, len(removable)-1\n",
    "        while left <= right:\n",
    "            mid = (left + right)//2\n",
    "            removed = set(removable[:mid+1])\n",
    "            if self.check(s, p, removed):\n",
    "                left = mid + 1\n",
    "                res = max(res, left)\n",
    "            else:\n",
    "                right = mid - 1\n",
    "        return res\n",
    "    \n",
    "    def check(self, s: str, p: str, removed: set) -> bool:\n",
    "        i, j = 0, 0\n",
    "        while i < len(s) and j < len(p):\n",
    "            if i in removed or s[i] != p[j]:\n",
    "                i += 1\n",
    "            else:\n",
    "                i += 1\n",
    "                j += 1\n",
    "        return j == len(p)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumRemovals(self, s: str, p: str, removable: List[int]) -> int:\n",
    "        left = 0\n",
    "        right = len(removable)+1\n",
    "        def check(idxs):\n",
    "            i = j = 0\n",
    "            while i < len(s) and j < len(p):\n",
    "                if i in idxs:\n",
    "                    i += 1\n",
    "                    continue\n",
    "                if s[i] == p[j]:\n",
    "                    i += 1\n",
    "                    j += 1\n",
    "                else:\n",
    "                    i += 1\n",
    "            return j == len(p)\n",
    "        while left < right:\n",
    "            mid = (left+right) >> 1\n",
    "            idxs = set(removable[:mid])\n",
    "            if not check(idxs):\n",
    "                right = mid\n",
    "            else:\n",
    "                left = mid + 1\n",
    "        return left-1\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumRemovals(self, s: str, p: str, removable: List[int]) -> int:\n",
    "        n1, n2 = len(s), len(p)\n",
    "        l, r = 0, len(removable)\n",
    "        while l < r: # 找寻的是右边界\n",
    "            \n",
    "            mid = (l + r + 1) // 2\n",
    "            has_del = set(removable[:mid])\n",
    "            p1 = p2 = 0\n",
    "            while p1 < n1 and p2 < n2:\n",
    "                if p1 not in has_del and p[p2] == s[p1]: p2 += 1\n",
    "                p1 += 1\n",
    "\n",
    "            if p2 == n2: #是可行解\n",
    "                l = mid \n",
    "            else:\n",
    "                r = mid - 1\n",
    "        \n",
    "        return l"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumRemovals(self, s: str, p: str, removable: List[int]) -> int:\n",
    "\n",
    "        def check(ceil):\n",
    "            i = 0\n",
    "            for x in range(n):\n",
    "                if rem.get(x, n) >= ceil and s[x] == p[i]:\n",
    "                    i += 1\n",
    "                if i == k:\n",
    "                    return True\n",
    "            return False\n",
    "\n",
    "        rem = {ind: i for i, ind in enumerate(removable)}\n",
    "\n",
    "        n = len(s)\n",
    "        k = len(p)\n",
    "        m = len(removable)\n",
    "        low = 0\n",
    "        high = m\n",
    "        while low<high-1:\n",
    "            mid = low+(high-low)//2\n",
    "            if check(mid):\n",
    "                low = mid\n",
    "            else:\n",
    "                high = mid\n",
    "        return high if check(high) else low"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "\n",
    "# 1 <= p.length <= s.length <= 105\n",
    "# removable 中的元素 互不相同\n",
    "\n",
    "# 返回你可以找出的 最大 k ，满足在移除字符后 p 仍然是 s 的一个子序列。\n",
    "class Solution:\n",
    "    def maximumRemovals(self, s: str, p: str, removable: List[int]) -> int:\n",
    "        mp = {x: i for i, x in enumerate(removable)}\n",
    "\n",
    "        def check(x):\n",
    "            \"\"\"Return True if p is a subseq of s after x removals.\"\"\"\n",
    "            k = 0\n",
    "            for i, ch in enumerate(s):\n",
    "                if mp.get(i, 0x7FFFFFFF) < x:\n",
    "                    continue\n",
    "                if k < len(p) and ch == p[k]:\n",
    "                    k += 1\n",
    "            return k == len(p)\n",
    "\n",
    "        left, right = -1, len(removable)\n",
    "        while left <= right:\n",
    "            mid = (left + right) >> 1\n",
    "            if check(mid):\n",
    "                left = mid + 1\n",
    "            else:\n",
    "                right = mid - 1\n",
    "        return right"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumRemovals(self, s: str, p: str, removable: List[int]) -> int:\n",
    "        s=list(s)\n",
    "        left,right=0,len(removable)+1\n",
    "        def check(s,p,reset):\n",
    "            if not p:return True\n",
    "            i,j=0,0\n",
    "            while i<len(s) and j<len(p):\n",
    "                if s[i]==p[j] and i not in reset:\n",
    "                    i+=1\n",
    "                    j+=1\n",
    "                else:\n",
    "                    i+=1\n",
    "                if j==len(p):return True\n",
    "            return False\n",
    "        # if check(s,p,set(removable)):return len(removable)\n",
    "        while left<right:\n",
    "            mid=left+(right-left)//2\n",
    "            reset=set(removable[0:mid])\n",
    "            if check(s,p,reset):\n",
    "                left=mid+1\n",
    "            else:\n",
    "                right=mid\n",
    "        return left-1\n",
    "# class Solution:\n",
    "#     def maximumRemovals(self, s: str, p: str, removable: List[int]) -> int:\n",
    "#         ns, np = len(s), len(p)\n",
    "#         n = len(removable)\n",
    "#         # 辅助函数，用来判断移除 k 个下标后 p 是否是 s_k 的子序列\n",
    "#         def check(k: int) -> bool:\n",
    "#             state = [True] * ns   # s 中每个字符的状态\n",
    "#             for i in range(k):\n",
    "#                 state[removable[i]] = False\n",
    "#             # 匹配 s_k 与 p \n",
    "#             j = 0\n",
    "#             for i in range(ns):\n",
    "#                 # s[i] 未被删除且与 p[j] 相等时，匹配成功，增加 j\n",
    "#                 if state[i] and s[i] == p[j]:\n",
    "#                     j += 1\n",
    "#                     if j == np:\n",
    "#                         return True\n",
    "#             return False\n",
    "        \n",
    "#         # 二分查找\n",
    "#         l, r = 0, n + 1\n",
    "#         while l < r:\n",
    "#             mid = l + (r - l) // 2\n",
    "#             if check(mid):\n",
    "#                 l = mid + 1\n",
    "#             else:\n",
    "#                 r = mid\n",
    "#         return l - 1\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumRemovals(self, s: str, p: str, removable: List[int]) -> int:\n",
    "        def check(s, p):\n",
    "            i, j = 0, 0\n",
    "            while i < m and j < n:\n",
    "                while (i < m and s[i] != p[j]) or i in dic:\n",
    "                    i += 1\n",
    "                if i == m or s[i] != p[j]:\n",
    "                    return False\n",
    "                i += 1\n",
    "                j += 1\n",
    "            return j == n\n",
    "        \n",
    "            \n",
    "        m, n = len(s), len(p)\n",
    "        s, p = list(s), list(p)\n",
    "        res = 0\n",
    "        \n",
    "        i, j = 1, len(removable)\n",
    "        while i <= j:\n",
    "            mid = i + (j - i) // 2\n",
    "            dic = set(removable[:mid])\n",
    "            if check(s, p):\n",
    "                i = mid + 1\n",
    "            else:\n",
    "                j = mid - 1\n",
    "        \n",
    "        return j"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumRemovals(self, s: str, p: str, removable: List[int]) -> int:\n",
    "        left,right = 0,len(removable)-1\n",
    "        res = None\n",
    "\n",
    "        while left <= right:\n",
    "            mid = left + (right-left)//2\n",
    "            temp_st = set(removable[:mid+1])\n",
    "            if self.check_subseq(s,p,temp_st):\n",
    "                left = mid + 1\n",
    "                res = mid\n",
    "            else:\n",
    "                right = mid - 1 \n",
    "        if res != None:\n",
    "            return res+1\n",
    "        return 0\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "#abcacb\n",
    "# (a)(b)c(a)cb\n",
    "    def check_subseq(self,s,p,st):\n",
    "        pt = 0\n",
    "        for i,c in enumerate(s):\n",
    "            if pt >= len(p):\n",
    "                return True\n",
    "            if c == p[pt] and i not in st:\n",
    "                pt += 1\n",
    "        return True if pt ==len(p) else False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumRemovals(self, s: str, p: str, removable: List[int]) -> int:\n",
    "        n = len(s)\n",
    "        remove_idx = defaultdict(lambda: inf)\n",
    "        for i, v in enumerate(removable):\n",
    "            remove_idx[v] = i\n",
    "\n",
    "        def check(k):\n",
    "            i = 0\n",
    "            for c in p:\n",
    "                while i < n and (s[i] != c or remove_idx[i] <= k - 1):  # 直到符合\n",
    "                    i += 1\n",
    "                if i == n:\n",
    "                    return False\n",
    "                i += 1\n",
    "            return True\n",
    "\n",
    "        lo, hi = 0, len(removable)\n",
    "        while lo < hi:\n",
    "            mid = lo + hi+1 >> 1\n",
    "            if check(mid):\n",
    "                lo = mid\n",
    "            else:\n",
    "                hi = mid - 1\n",
    "        return lo\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumRemovals(self, s: str, p: str, removable: List[int]) -> int:\n",
    "        def check(x):\n",
    "            d = Counter(removable[:x])\n",
    "            n = len(s)\n",
    "            i = 0\n",
    "            for c in p:\n",
    "                while i < n and (s[i] != c or d[i] > 0):\n",
    "                    i += 1\n",
    "                if i < n:\n",
    "                    i += 1\n",
    "                else: return False\n",
    "            return True\n",
    "        \n",
    "        left, right = 0, len(removable)\n",
    "        while left <= right:\n",
    "            mid = (left + right)//2 \n",
    "            if check(mid):\n",
    "                left = mid + 1\n",
    "            else:\n",
    "                right = mid - 1\n",
    "        return right\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumRemovals(self, s: str, p: str, removable: List[int]) -> int:\n",
    "        def ck(x): \n",
    "            c = Counter(removable[:x])\n",
    "            ss = \"\"\n",
    "            for i, cc in enumerate(s):\n",
    "                if i not in c:\n",
    "                    ss += cc \n",
    "            i = j = 0\n",
    "            m, n = len(ss), len(p)\n",
    "            while i < m and j < n:\n",
    "                if ss[i] == p[j]:\n",
    "                    i += 1\n",
    "                    j += 1\n",
    "                else:\n",
    "                    i += 1\n",
    "            if j == n: return True\n",
    "            return False\n",
    "\n",
    "        l, r = 0, len(removable)\n",
    "        while l < r:\n",
    "            mid = l + r + 1 >> 1\n",
    "            if ck(mid): l = mid \n",
    "            else: r = mid - 1 \n",
    "\n",
    "        return l "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumRemovals(self, s: str, p: str, removable: List[int]) -> int:\n",
    "\n",
    "        def is_subsequence(s, p): \n",
    "            i = j = 0 \n",
    "            m, n = len(s), len(p) \n",
    "            while i < m and j < n: \n",
    "                if s[i] == p[j]: j += 1 \n",
    "                i += 1 \n",
    "            return j == n\n",
    "\n",
    "        def ck(x): \n",
    "            c = Counter(removable[:x])\n",
    "            ss = \"\"\n",
    "            for i, cc in enumerate(s):\n",
    "                if i not in c:\n",
    "                    ss += cc \n",
    "            return is_subsequence(ss, p)\n",
    "\n",
    "        l, r = 0, len(removable)\n",
    "        while l < r:\n",
    "            mid = l + r + 1 >> 1\n",
    "            if ck(mid): l = mid \n",
    "            else: r = mid - 1 \n",
    "        return l "
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
